#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef string vextype;
const int n = 6;
int visited[n];
typedef struct AMGraph
{
    vextype vexs[n];
    int arcs[n][n];
    int vexnum, arcnum;
} AMGraph;
struct Edge
{
    int fromvex;  // U集中顶点序号
    int endvex;   // V-U集中顶点序号
    float length; //边的权值
    Edge() {}
};

void create(AMGraph &G)
{
    G.arcnum = 10;
    G.vexnum = 6;
    float arcs[n][n] = {
        {10000, 6, 1, 5, 10000, 10000},
        {6, 10000, 5, 10000, 3, 10000},
        {1, 5, 10000, 7, 5, 4},
        {5, 10000, 7, 10000, 10000, 2},
        {10000, 3, 5, 10000, 10000, 6},
        {10000, 10000, 4, 2, 6, 10000}};
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            
            G.arcs[i][j] = arcs[i][j];
        }
    }
}

vector<Edge> PRIM(AMGraph &G)
{
    vector<Edge> T(n);

    for (int j = 1; j < G.vexnum; j++)
    {
        T[j - 1] = *(new Edge());
        T[j - 1].fromvex = 1;
        T[j - 1].endvex = j + 1;
        T[j - 1].length = G.arcs[0][j];
    }
    int m;
    for (int k = 0; k < G.vexnum - 1; k++)
    {
        float min = 10000;
        for (int j = k; j < G.vexnum - 1; j++)
            if (T[j].length < min)
            {
                min = T[j].length;
                m = j;
            }
        Edge e = T[m];
        T[m] = T[k];
        T[k] = e;
        int v = T[k].endvex;
        for (int j = k + 1; j < G.vexnum - 1; j++)
        {
            float d = G.arcs[v - 1][T[j].endvex - 1];
            if (d < T[j].length)
            {
                T[j].length = d;
                T[j].fromvex = v;
            }
        }
    }
    return T;
}

int main(int argc, char const *argv[])
{
    AMGraph G;

    create(G);

    vector<Edge> T;
    T = PRIM(G);
    
    cout << "fromvex\tendvex\tlength" << endl;
    for (int i = 0; i < G.vexnum - 1; i++)
    {
        cout << "\t" << T[i].fromvex << "\t" << T[i].endvex << "\t" << T[i].length << endl;
    }

    return 0;
}
